//给你一个字符串 s ，它只包含三种字符 a, b 和 c 。 
//
// 请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。 
//
// 
//
// 示例 1： 
//
// 输入：s = "abcabc"
//输出：10
//解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", 
//"bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
// 
//
// 示例 2： 
//
// 输入：s = "aaacb"
//输出：3
//解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
// 
//
// 示例 3： 
//
// 输入：s = "abc"
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 3 <= s.length <= 5 x 10^4 
// s 只包含字符 a，b 和 c 。 
// 
//
// Related Topics 哈希表 字符串 滑动窗口 👍 129 👎 0

package leetcode.editor.cn;
//java:包含所有三种字符的子字符串数目
public class Q1358NumberOfSubstringsContainingAllThreeCharacters {
    public static void main(String[] args){
        Solution solution = new Q1358NumberOfSubstringsContainingAllThreeCharacters().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numberOfSubstrings(String s) {
        int len = s.length(), left = 0, res = 0;
        // 记录字母出现的次数
        int[] counts = new int[3];
        char[] chars = s.toCharArray();
        for (int right = 0; right < len; right++) {
            counts[chars[right] - 'a']++;
            // 符合条件, 缩小左边界
            while (counts[0] > 0 && counts[1] > 0 && counts[2] > 0) {
                counts[chars[left] - 'a']--;
                left++;
            }
            // right是子字符的右边界，左边界在[0, left - 1]的都符合条件
            res += left;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}